591. Коробка с кирпичами

Играя с кирпичами, Боб выстраивает стопки разной высоты. Алиса хочет переложить минимальное количество кирпичей так, чтобы все стопки имели одинаковую высоту.

Вход. Состоит из нескольких тестов. Первая строка каждого теста содержит количество стопок n. Во второй строке следуют n чисел – высоты стопок h_i . Известно, что 1 £ n £ 50, 1 £ h_i £ 100. Общее количество кирпичей всегда делится на количество стопок. Признак конца входных данных n = 0.

Выход. Для каждого теста вывести его номер и сообщение ‘The minimum number of moves is k.’, где k – минимальное количество кирпичей которое надо переложить, чтобы уравнять стопки. После каждого теста выводить пустую строку.

Пример входа

6
5 2 4 1 7 5
0
 

Пример выхода

Set #1
The minimum number of moves is 5.
 

РЕШЕНИЕ

математика

Анализ алгоритма

Вычисляем общее количество кирпичей и делим его на количество стопок. Получаем высоту уравненных стопок s. Для решения задачи следует переложить все кирпичи со стопок, высоты которых больше s в стопки с высотами меньше s. Количество перекладываемых кирпичей равно

Пример

Данные теста показаны на рисунке выше. Для уравнивания стопок следует переложить 1 кирпич с первой стопки во вторую, 1 кирпич с шестой стопки во вторую и 3 кирпича с пятой стопки в четвертую. Всего необходимо переложить 5 кирпичей.

Реализация алгоритма

Переменная c содержит номер текущего теста. Инициализируем c = 1. Читаем значение n, высоты стопок в массив m[50] и вычисляем общее количество кирпичей в переменной summa.

while(scanf("%d",&n),n)

{

for(summa = res = i = 0; i < n; i++)

{

scanf("%d",&m[i]);

summa += m[i];

}

Полученную сумму делим на n, получаем количество кирпичей, которое должно находиться в каждой уравненной стопке.

summa = summa / n;

Вычисляем минимальное количество кирпичей, которое следует переложить для уравнивания стопок, и печатаем ответ. После каждого теста выводим пустую строку.

for(i = 0; i < n; i++)

if (m[i] > summa) res += m[i] - summa;

printf("Set #%d\nThe minimum number of moves is %d.\n\n",c++,res);

}